Encoding methods, commonly called halftoning, are used to reduce the number of quantization levels per pixel in a digital image while maintaining the gray appearance of the image at normal reading distance. Halftoning techniques are widely employed in the printing and display of digital images. Halftoning techniques are necessary because the physical processes involved are binary in nature or the processes have been restricted to binary operation for reason of cost, speed-memory, or stability in the presence of process fluctuations. Examples of such processes are: most printing presses; ink jet printers; binary cathode ray tube displays; and laser xerography.
In the digital reproduction of documents, image information, be it color, black, or white, is commonly generated in a bitmap format where the bitmap comprises a plurality of continuous tone or gray level pixels, i.e., pixels that are defined by digital values, each value representing a gray level among a number of gray levels. Thus, in an 8 bit system, 256 levels of gray are present, where each level represents an increment of gray between white and black. Each separation includes 256 levels of information and there may be more than 16 million colors defined by a gray bitmap. Usually, bitmaps in such a gray level format are unprintable by standard printers. Standard printers print in a limited number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, for example, four in the quaternary case. Accordingly, it is a limited number of levels that are printable. Besides gray level information derived by scanning, certain processing techniques such as those described, for example, in U.S. Pat. No. 5,226,094 to Eschbach, may produce gray level data requiring quantization for printing.
A standard method of quantizing gray level pixel values to binary level pixel values is through dithering or screening processes. In such arrangements, over a given area having a number of gray pixels therein, each pixel value of an array of gray level pixels within the area is compared to one of a set of pre-selected thresholds as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the screen matrix will be exceeded, i.e., the image value at that specific location is larger than the values stored in the dither matrix for that same location, while the remaining elements are allowed to remain white, dependent on the actual physical quantity described by the data. The effect of the distribution of black and white over the halftone cell is integrated by the human eye as gray. A trade-off is required between the number of gray level increments representable by a screen cell, versus the size or frequency of the cell. While it is desirable to have as many gray levels as possible representable by a screen cell, such a requirement increases the size of the cell until its repetition across an image becomes visible. However, with a smaller cell, which can be repeated at high frequency across a page, only a relatively small number of gray levels can be represented.
Algorithms that convert gray images to binary or other number of level images without repeating patterns exist, and include among them error diffusion, as taught, for example, in "An Adaptive Algorithm for Spatial Grayscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976). Another more elaborate error diffusion technique is taught by U.S. Pat. No. 5,045,952 to Eschbach. Error diffusion tends to suffer from a characteristic "worming" defect. One method of reducing the worming artifact in an error diffusion process that has been noted is to distribute error along a space filling curve, such as Hilbert, Peano or Murray Curves. See, for example, "Using Peano Curves for Bilevel Display of Continuous-tone Images", by Witten et al., IEEE Comp. Graph. and App. Vol. 2, No. 5, pp. 47-52 (1982); "Naive Halftoning" by A/J/ Cole, Proceedings of CGI '90, Springer Verlag pp. 203-222 (1990); and "Three Plus Five Makes Eight: A simplified Approach to Halftoning" by Wyvill et al., Proceedings of CGI '91 Scientific Visualization of Physical Phenomena, pp. 379-392 (1991). Unfortunately, space filing curves present complex processing order, see, for example, "Digital halftoning with Space Filling Curves" by L. Valhi et al., Computer Graphics, Vol. 25 No. 4, pp. 81-90 (1991), while, in view of the operation of printers and most image processors, it would be highly desirable to work in scan line order. Error diffusion is often unusable by certain reproduction processes, such as electrophotography, because it tends to produce isolated spots that are not reproducible. In such, cases, screening is used with threshold sets arranged to cluster spots together into larger printable dots. Error diffusion is also an inherently sequential process that does not lend itself to parallel processing, while screening.
Even with the implementation of halftoning techniques to digital image processing, the appearance of visible image artifacts still exists in a rendered image. During object oriented halftoning an artifact is created which is very visible to the eye when the halftone dot structure is switched in the middle of the line. In rendering images, the need arises to halftone different objects with different halftone dots, depending upon the classification of the object, such as text, pictures, etc. When doing this it is required that multiple halftone dots are to be used. As currently done this generates an objectionable artifact at the boundary between the two halftone dots. Therefore, the object of this invention is to provide a method of minimizing visible image artifacts on rendered images.
All of the references cited herein are incorporated by reference for their teachings.